/**
 * 
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * 
 * n == height.length
 * 1 <= n <= 2 * 104
 * 0 <= height[i] <= 105
 */


 class Solution {
public:
    //method 1
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int>pre_max(n),suf_max(n);
        pre_max.front() = height.front(),suf_max.back() = height.back();
        for(int i = 1;i < n;i++){
            pre_max[i] = max(pre_max[i - 1],height[i]);
        }
        for(int i = n - 2;i >= 0;i--){
            suf_max[i] = max(suf_max[i + 1],height[i]);
        }
        int ans = 0;
        for(int i = 0;i < n;i++){
            ans += min(pre_max[i],suf_max[i]) - height[i];
        }
        return ans;
    }

    //method 2
    int trap(vector<int>& height) {
        int ans = 0,n = height.size();
        int left = 0,right = n - 1;
        int pre_max = 0,suf_max = 0;
        while(left < right){
            pre_max = max(pre_max,height[left]);
            suf_max = max(suf_max,height[right]);
            ans += pre_max < suf_max ? pre_max - height[left++] : suf_max - height[right--];
        }
        return ans;
    }

    //method 3
    int trap(vector<int>& height) {
        int ans = 0,n = height.size();
        stack<int>st;
        for(int i = 0;i < n;i++){
            auto h = height[i];
            while(!st.empty() and height[st.top()] <= h){
                int bottom_h = height[st.top()];
                st.pop();
                if(st.empty())break;
                int left = st.top();
                int dh = min(height[left],height[i]) - bottom_h;
                ans += dh * (i - left - 1);
            }
            st.push(i);
        }
        return ans;
    }
};